<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="utf-8">
  

  
  <title>算法导论-第二章 | 章军的博客</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta name="description" content="#　伪代码的约定">
<meta name="keywords" content="pseudocode">
<meta property="og:type" content="article">
<meta property="og:title" content="算法导论-第二章">
<meta property="og:url" content="http://octopuscloud.top/2019/03/03/二章-基本算法/index.html">
<meta property="og:site_name" content="章军的博客">
<meta property="og:description" content="#　伪代码的约定">
<meta property="og:locale" content="China">
<meta property="og:updated_time" content="2019-09-11T04:27:11.616Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="算法导论-第二章">
<meta name="twitter:description" content="#　伪代码的约定">
  
    <link rel="alternate" href="/atom.xml" title="章军的博客" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  <link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">章军的博客</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://octopuscloud.top"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main"><article id="post-二章-基本算法" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2019/03/03/二章-基本算法/" class="article-date">
  <time datetime="2019-03-03T06:50:05.000Z" itemprop="datePublished">2019-03-03</time>
</a>
    
  <div class="article-category">
    <a class="article-category-link" href="/categories/ReadNote/">ReadNote</a>
  </div>

  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="article-title" itemprop="name">
      算法导论-第二章
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>#　伪代码的约定<br><a id="more"></a></p>
<pre><code>1. 代码中的**缩进**表示程序中的分程序块 .
2. 符号 ▷后面为注释 .
3. 符号 ←代表赋值　。
4. 如果变量仅作用于局部　，使用局部变量　。
5. 数组有 A[index] 来访问　。
6. 无特殊说明　，参数传递都是值传递　。
7. and 和　or 运算符都有短路功能　。
</code></pre><h1 id="代码分析的基本概念"><a href="#代码分析的基本概念" class="headerlink" title="代码分析的基本概念"></a>代码分析的基本概念</h1><ul>
<li><p>输入规模</p>
<p>  与具体的问题有关，在数组的排序算法中，数据规模为数组的长度；算法的输入为图时，输入规模用定点数和边数来标示。</p>
</li>
<li><p>运行时间</p>
<p>  在指定特定输入时，算法所执行的基本操作数。</p>
<ol>
<li>最坏运行时间<br> 对于输入规模为n的数组，最长的运行时间。最长的运行时间。</li>
<li>平均运行事件<br> 对于输入规模为n的数组，运行时间的数学期望。</li>
</ol>
</li>
<li><p>增长的量级</p>
<p>  在输入规模为n的运行时间中，去最高次项作为增长的量级。</p>
</li>
</ul>
<h1 id="两种排序算法"><a href="#两种排序算法" class="headerlink" title="两种排序算法"></a>两种排序算法</h1><h2 id="插入法"><a href="#插入法" class="headerlink" title="插入法"></a>插入法</h2><pre><code>插入法使用的时增量法，在已经排好顺序的子序列 A[1...j-1]中插入 A[j]，形成排好的子序列 A[1...j]。
最坏运行时间为: θ(n^2).
平均运行时间: θ(nlgn)

InsertSort - A[1...n]
for i ←2 to length[A]
    key ←A[i]
    j = i
    while i &gt; 0 and A[i] &gt; key
        A[i] = A[i-1]
        i -= 1
    A[i] = key
</code></pre><p>算法实现 [InsertSort][2]</p>
<h2 id="合并法"><a href="#合并法" class="headerlink" title="合并法"></a>合并法</h2><pre><code>将需要排序的序列分为两个子序列(此处为递归的调用自身，直到子序列长度为1时结束)，合并两个排好顺序的子序列，
完成父序列的排序。
运行时间为: θ(nlgn)

l ←0
m ←n/2
r ←length[A]
MegerSort - A[1...n], l, m, r
if m - l ≥1
    sub_m = l+(m-l)/2
    MegerSort(l,sub_m,m)
if r-m ≥1
    sub_m = m+(r-m)/2
    MegerSort(m,sub_m,r)
create a new arry new[1,r-l]

left_len ←l
right_len ←m
for i ←0 to r-l and ( left_len &lt;= m or right &lt;= r)
    if A[left_len] &gt; A[right_len] 
        new[i] ←A[right_len]
        right_len += 1
    else 
        new[i] ←A[left_len]
        left_len += 1
</code></pre><h2 id="算法实现-MergeSort-2"><a href="#算法实现-MergeSort-2" class="headerlink" title="算法实现 [MergeSort][2]"></a>算法实现 [MergeSort][2]</h2><ol>
<li><a href="https://zh.wikipedia.org/zh-hk/Pascal_(%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80)" target="_blank" rel="noopener">https://zh.wikipedia.org/zh-hk/Pascal_(%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80)</a></li>
<li><a href="https://github.com/singledo/SortCode" target="_blank" rel="noopener">https://github.com/singledo/SortCode</a></li>
</ol>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://octopuscloud.top/2019/03/03/二章-基本算法/" data-id="ck471vq1c001i32fzgr8orhv7" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/pseudocode/">pseudocode</a></li></ul>

    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2019/03/10/三章-标记符号/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          算法导论-第三章
        
      </div>
    </a>
  
  
    <a href="/2019/03/02/vim-配置/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">vim 配置</div>
    </a>
  
</nav>

  
</article>

</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Categories</h3>
    <div class="widget">
      <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/RFC/">RFC</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/RFC-protocol/">RFC protocol</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ReadNote/">ReadNote</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/linux/">linux</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/protocols/">protocols</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/tools/">tools</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/C/">C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Data-Struct/">Data Struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Ethernet-II/">Ethernet II</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Frame-Format/">Frame Format</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/I2C/">I2C</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/IPv6/">IPv6</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Neighbour-Discover-Protocol/">Neighbour Discover Protocol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/RFC/">RFC</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/SNMP/">SNMP</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/arthmetic/">arthmetic</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/cgdb/">cgdb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/chapter-15/">chapter 15</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/data-struct/">data struct</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/deb/">deb</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/defalt-path-for-so-file/">defalt path for so file</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/editer/">editer</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/file-system/">file system</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/gdb-debug/">gdb debug</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/hash/">hash</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux/">linux</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/linux-driver/">linux driver</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/platform-bus/">platform bus</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pointer-array/">pointer, array</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pseudocode/">pseudocode</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/rb-tree/">rb tree</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sort/">sort</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/ssh-key/">ssh key</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/symbol/">symbol</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tool/">tool</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/tools/">tools</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/图/">图</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/通信协议/">通信协议</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/C/" style="font-size: 10px;">C</a> <a href="/tags/Data-Struct/" style="font-size: 10px;">Data Struct</a> <a href="/tags/Ethernet-II/" style="font-size: 10px;">Ethernet II</a> <a href="/tags/Frame-Format/" style="font-size: 10px;">Frame Format</a> <a href="/tags/I2C/" style="font-size: 10px;">I2C</a> <a href="/tags/IPv6/" style="font-size: 15px;">IPv6</a> <a href="/tags/Neighbour-Discover-Protocol/" style="font-size: 10px;">Neighbour Discover Protocol</a> <a href="/tags/RFC/" style="font-size: 10px;">RFC</a> <a href="/tags/SNMP/" style="font-size: 10px;">SNMP</a> <a href="/tags/arthmetic/" style="font-size: 10px;">arthmetic</a> <a href="/tags/cgdb/" style="font-size: 10px;">cgdb</a> <a href="/tags/chapter-15/" style="font-size: 10px;">chapter 15</a> <a href="/tags/data-struct/" style="font-size: 15px;">data struct</a> <a href="/tags/deb/" style="font-size: 10px;">deb</a> <a href="/tags/defalt-path-for-so-file/" style="font-size: 10px;">defalt path for so file</a> <a href="/tags/editer/" style="font-size: 10px;">editer</a> <a href="/tags/file-system/" style="font-size: 10px;">file system</a> <a href="/tags/gdb-debug/" style="font-size: 10px;">gdb debug</a> <a href="/tags/hash/" style="font-size: 10px;">hash</a> <a href="/tags/linux/" style="font-size: 20px;">linux</a> <a href="/tags/linux-driver/" style="font-size: 10px;">linux driver</a> <a href="/tags/platform-bus/" style="font-size: 10px;">platform bus</a> <a href="/tags/pointer-array/" style="font-size: 10px;">pointer, array</a> <a href="/tags/pseudocode/" style="font-size: 10px;">pseudocode</a> <a href="/tags/rb-tree/" style="font-size: 10px;">rb tree</a> <a href="/tags/sort/" style="font-size: 20px;">sort</a> <a href="/tags/ssh-key/" style="font-size: 10px;">ssh key</a> <a href="/tags/symbol/" style="font-size: 10px;">symbol</a> <a href="/tags/tool/" style="font-size: 10px;">tool</a> <a href="/tags/tools/" style="font-size: 10px;">tools</a> <a href="/tags/图/" style="font-size: 10px;">图</a> <a href="/tags/通信协议/" style="font-size: 10px;">通信协议</a>
    </div>
  </div>

  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/12/">December 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/11/">November 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/10/">October 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/09/">September 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/08/">August 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/07/">July 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/06/">June 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/05/">May 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/04/">April 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2019/12/15/TMUX-使用/">TMUX-使用</a>
          </li>
        
          <li>
            <a href="/2019/11/02/linux-platform-bus-总线分析/platform/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/11/02/十二章-二叉搜索树/">算法导论-第十二章 二叉查找树</a>
          </li>
        
          <li>
            <a href="/2019/11/02/SegmentationFault-Debug/">(no title)</a>
          </li>
        
          <li>
            <a href="/2019/10/19/linux-platform-bus-总线分析/">linux platform bus 总线分析</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2019 zhangjun<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


  <link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
  <script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>



  </div>
</body>
</html>